package binarytree

type TreeNode struct{
	Val int
	Left,Right *TreeNode
}

// 根据中序和后序遍历构建二叉树
// 中序：根节点在中间 分割左右
// 后序： 根节点在末尾
// 所以，根据后序序列找到根，然后左右子树可以确认
func buildTree(inorder []int, postorder []int) *TreeNode {
	// 递归版本
	if len(inorder) != len(postorder) {
		return nil   
	}
	if len(inorder)==0 || len(postorder)==0 {
		return nil
	}

	// 建立根节点
	root := &TreeNode{Val:postorder[len(postorder)-1]}  
	// 建立左右子树
	idx := indexOf(inorder,root.Val)  // 查找根在中序序列中的位置  （如果出现多个根值怎么办？--题目已假设）

	root.Left = buildTree(inorder[:idx], postorder[:idx])
	root.Right = buildTree(inorder[idx+1:], postorder[idx:len(postorder)-1])
	return root
}
// 查找val在数组中的位置
func indexOf(inorder []int, val int) int {
	// 一次遍历 
	for i,v := range inorder {
		if v==val {
			return i
		}
	}
	return -1
}
